216. Combination Sum III
Medium

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Example 4:

Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.

Example 5:

Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
There are no other valid combinations.

 

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 60
Accepted
233,385
Submissions
380,857
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.87 (31 votes)

Premium

Solution


Approach 1: Backtracking

Intuition

The problem asks us to come up with some fixed-length combinations that meet certain conditions.

To solve the problem, it would be beneficial to build a combination by hand.

If we represent the combination as an array, we then could fill the array one element at a time.

For example, given the input k=3k=3 and n=9n=9, i.e. the size of the combination is 3, and the sum of the digits in the combination should be 9. Here are a few steps that we could do:

  • 1). We could pick a digit for the first element in the combination. Initially, the list of candidates is [1, 2, 3, 4, 5, 6, 7, 8. 9] for any element in the combination, as stated in the problem. Let us pick 1 as the first element. The current combination is [1].

first element

  • 2). Now that we picked the first element, we have two more elements to fill in the final combination. Before we proceed, let us review the conditions that we should fullfil for the next steps.

    • Since we've already picked the digit 1, we should exclude the digit from the original candidate list for the remaining elements, in order to ensure that the combination does not contain any duplicate digits, as required in the problem.

    • In addition, the sum of the remaining two elements should be 91=89 - 1 = 8.

  • 3). Based on the above conditions, for the second element, we could have several choices. Let us pick the digit 2, which is not a duplicate of the first element, plus it does not exceed the desired sum (i.e. 88) neither. The combination now becomes [1, 2].

second element

  • 4). Now for the third element, with all the constraints, it leaves us no choice but to pick the digit 6 as the final element in the combination of [1, 2, 6].

third element

  • 5). As we mentioned before, for the second element, we could have several choices. For instance, we could have picked the digit 3, instead of the digit 2. Eventually, it could lead us to another solution as [1, 3, 5].

  • 6). As one can see, for each element in the combination, we could revisit our choices, and try out other possibilities to see if it leads to a valid solution.

If you have followed the above steps, it should become evident that backtracking would be the technique that we could use to come up an algorithm for this problem.

backtrack

Indeed, we could resort to backtracking, where we try to fill the combination one element at a step. Each choice we make at certain step might lead us to a final solution. If not, we simply revisit the choice and try out other choices, i.e. backtrack.

Algorithm

There are many ways to implement a backtracking algorithm. One could also refer to our Explore card where we give some examples of backtracking algorithms.

To implement the algorithm, one could literally follow the steps in the Intuition section. However, we would like to highlight a key trick that we employed, in order to ensure the non-redundancy among the digits within a single combination, as well as the non-redundancy among the combinations.

The trick is that we pick the candidates in order. We treat the candidate digits as a list with order, i.e. [1, 2, 3, 4, 5, 6, 7, 8. 9]. At any given step, once we pick a digit, e.g. 6, we will not consider any digits before the chosen digit for the following steps, e.g. the candidates are reduced down to [7, 8, 9].

With the above strategy, we could ensure that a digit will never be picked twice for the same combination. Also, all the combinations that we come up with would be unique.

Here are some sample implementations based on the above ideas.

Complexity Analysis

Let KK be the number of digits in a combination.

  • Time Complexity: O(9!K(9K)!)\mathcal{O}(\frac{9! \cdot K}{(9-K)!})

    • In a worst scenario, we have to explore all potential combinations to the very end, i.e. the sum nn is a large number (n>99n > 9 * 9). At the first step, we have 99 choices, while at the second step, we have 88 choices, so on and so forth.

    • The number of exploration we need to make in the worst case would be P(9,K)=9!(9K)!P(9, K) = \frac{9!}{(9-K)!}, assuming that K<=9K <= 9. By the way, KK cannot be greater than 9, otherwise we cannot have a combination whose digits are all unique.

    • Each exploration takes a constant time to process, except the last step where it takes O(K)\mathcal{O}(K) time to make a copy of combination.

    • To sum up, the overall time complexity of the algorithm would be 9!(9K)!O(K)=O(9!K(9K)!) \frac{9!}{(9-K)!} \cdot \mathcal{O}(K) = \mathcal{O}(\frac{9! \cdot K}{(9-K)!}).

  • Space Complexity: O(K)\mathcal{O}(K)

    • During the backtracking, we used a list to keep the current combination, which holds up to KK elements, i.e. O(K)\mathcal{O}(K).

    • Since we employed recursion in the backtracking, we would need some additional space for the function call stack, which could pile up to KK consecutive invocations, i.e. O(K)\mathcal{O}(K).

    • Hence, to sum up, the overall space complexity would be O(K)\mathcal{O}(K).

    • Note that, we did not take into account the space for the final results in the space complexity.


Report Article Issue

Comments: 21
mchall92's avatar
Read More

This is a question whose big O problem is more difficult and complex than the question itself...

48
Reply
Share
Report
cedrus's avatar
Read More

I think this problem involves combination. In terms of combination, the time complexity is O(C(9,k)) = O(9!/(k! * (9-k)!). There is no duplicate in each combination, and the order of numbers doesn't matter. It can be faster since all numbers sum up to n, and the case numbers added up more than n can return earlier.

30
Show 4 replies
Reply
Share
Report
clock330's avatar
Read More

I am confused by the time complexity analysis:

At the first step, we have 9 choices, while at the second step, we have 8 choices, so on and so forth.

It is true that we have 9 choices at the first step, but the number of choices in the second step depends on our choice in first step. If we choose 1 in step1, then we have 8 choices in step2, if we choose 6 in step1, we only have 3 choices in step2. So not all step2 has same 8 choices. And this applies to all remaining steps.

Saying that the time complexity is O(9!/(9 - K)!) is right though, but is this upper bound too high? Is this like saying O(n^2) is the upper bound of a linear algorithm? it is definitely true, but we can have more precise upper bound O(n).

On the other hand, this could be the O(1 + 2 + ... + n) = O(n^2) case. Can anyone help me?

PS: I tried k = [0:9], n = 45 (I think as long as n >= 45, it will exhaust all searches until comb.size() == k), and counted the number of times backtrack() was invoked (this includes every recursive call in the for loop). I compared the growth rate of this number with 9!/(9 - K)!:

k backtrack() invoked 9!/(9 - k)!
0 1 1
1 10 9
2 46 72
3 130 504
4 256 3024
5 382 15120
6 466 60480
7 502 181440
8 511 362880
9 512 362880

14
Show 5 replies
Reply
Share
Report
snibbets's avatar
Read More

The number of steps should actually be bounded by a constant because if n > 45 the result is always an empty list. If the algorithm returns [] whenever n > 45, the time complexity would be O(1).

6
Reply
Share
Report
rahulkun's avatar
Read More

time complexity of O(C(9,k)) makes intuitive sense. I don't know how to derive the time complexity above.

3
Reply
Share
Report
133c7's avatar
Read More

Wouldn't the time complexity be simply ~O(9Ck) rather than ~O(9Ck * k)? My reasoning was that, although it takes ~O(k) time to deeply copy the combination, not every branch in the recursion tree will need to copy the combination. In fact, it seemed to me that only a very small number of branch would end up copying the combination, as most branch will end up not arriving at the answer. But technically ~O(9Ck * k) is a correct loose upperbound.

Could anyone explain how to correctly reason about the time complexity?

3
Show 1 reply
Reply
Share
Report
magks's avatar
Read More

In the python version, line 7 -- why is it necessary to append(list(comb)) rather than just append(comb) ?

I tried it without wrapping comb and see that the result is appending an empty list to results but does anyone know why this is? Both type(comb) and type(list(comb)) return <class 'list'> and also the output of print(comb) and print(list(comb)) appear identical. print(comb == list(comb)) likewise results in True.

And yet results.append(comb) results in appending empty lists while results.append(list(comb)) actually does append the list as expected.

2
Show 4 replies
Reply
Share
Report
NeosDeus's avatar
Read More

Can you explain how does the trick guarantee each subset generated this way is unique?

1
Show 1 reply
Reply
Share
Report
KaitoKid56's avatar
Read More

Can anyone tell me why are we removing the last element on line 19?
Is it that in backtracking we have to remove ONLY the last element?

1
Show 5 replies
Reply
Share
Report
alvin-777's avatar
Read More

I don't know how should I estimate the time complexity of my solution below:

vector<vector<int>> combinationSum3(int k, int n) {
    if (!k || k > 9) return {};
    const vector<vector<int>> REF{{0, 1, 3, 6, 10, 15, 21, 28, 36, 45},
                                  {0, 9,17,24, 30, 35, 39, 42, 44, 45}};
    vector<vector<int>> ans;
    vector<int> buf(k, 0);
    for (int i = 0, sum = 0; i >= 0; ) {
        if (i == k - 1) {
            int r = n - sum;
            if (r > (i ? buf[i-1] : 0) && r < 10) {
                buf[i] = r;
                ans.push_back(buf);
            }
            --i;
            continue;
        }

        sum -= buf[i]++;
        int p = (i ? buf[i-1] : 0), r = n - sum, rc = k - i;
        if (buf[i] <= p) buf[i] = p + 1;
        if (buf[i] > 9 || p + rc > 9 || r < REF[0][p+rc] - REF[0][p] || r > REF[1][rc]) {
            buf[i--] = 0;
            continue;
        }
        sum += buf[i++];
    }
    return ans;
}

I tried to trim all the impossible branches as early as possible.
Then I counted how much "efforts" (number of loops) is needed for any k/n input:
(Since 45 is the largest sum from 1 to 9, for n > 45 the effort is always "1")

k1,n1:	1	| k1,n2:	1	| k1,n3:	1	| k1,n4:	1	| k1,n5:	1	| 
k1,n6:	1	| k1,n7:	1	| k1,n8:	1	| k1,n9:	1	| k1,n10:	1	| 
k1,n11:	1	| k1,n12:	1	| k1,n13:	1	| k1,n14:	1	| k1,n15:	1	| 
k1,n16:	1	| k1,n17:	1	| k1,n18:	1	| k1,n19:	1	| k1,n20:	1	| 
k1,n21:	1	| k1,n22:	1	| k1,n23:	1	| k1,n24:	1	| k1,n25:	1	| 
k1,n26:	1	| k1,n27:	1	| k1,n28:	1	| k1,n29:	1	| k1,n30:	1	| 
k1,n31:	1	| k1,n32:	1	| k1,n33:	1	| k1,n34:	1	| k1,n35:	1	| 
k1,n36:	1	| k1,n37:	1	| k1,n38:	1	| k1,n39:	1	| k1,n40:	1	| 
k1,n41:	1	| k1,n42:	1	| k1,n43:	1	| k1,n44:	1	| k1,n45:	1	| 

k2,n1:	1	| k2,n2:	1	| k2,n3:	19	| k2,n4:	19	| k2,n5:	19	| 
k2,n6:	19	| k2,n7:	19	| k2,n8:	19	| k2,n9:	19	| k2,n10:	19	| 
k2,n11:	19	| k2,n12:	19	| k2,n13:	19	| k2,n14:	19	| k2,n15:	19	| 
k2,n16:	19	| k2,n17:	19	| k2,n18:	1	| k2,n19:	1	| k2,n20:	1	| 
k2,n21:	1	| k2,n22:	1	| k2,n23:	1	| k2,n24:	1	| k2,n25:	1	| 
k2,n26:	1	| k2,n27:	1	| k2,n28:	1	| k2,n29:	1	| k2,n30:	1	| 
k2,n31:	1	| k2,n32:	1	| k2,n33:	1	| k2,n34:	1	| k2,n35:	1	| 
k2,n36:	1	| k2,n37:	1	| k2,n38:	1	| k2,n39:	1	| k2,n40:	1	| 
k2,n41:	1	| k2,n42:	1	| k2,n43:	1	| k2,n44:	1	| k2,n45:	1	| 

k3,n1:	1	| k3,n2:	1	| k3,n3:	1	| k3,n4:	1	| k3,n5:	1	| 
k3,n6:	35	| k3,n7:	35	| k3,n8:	35	| k3,n9:	49	| k3,n10:	49	| 
k3,n11:	49	| k3,n12:	61	| k3,n13:	61	| k3,n14:	61	| k3,n15:	71	| 
k3,n16:	71	| k3,n17:	71	| k3,n18:	79	| k3,n19:	63	| k3,n20:	49	| 
k3,n21:	43	| k3,n22:	33	| k3,n23:	25	| k3,n24:	23	| k3,n25:	1	| 
k3,n26:	1	| k3,n27:	1	| k3,n28:	1	| k3,n29:	1	| k3,n30:	1	| 
k3,n31:	1	| k3,n32:	1	| k3,n33:	1	| k3,n34:	1	| k3,n35:	1	| 
k3,n36:	1	| k3,n37:	1	| k3,n38:	1	| k3,n39:	1	| k3,n40:	1	| 
k3,n41:	1	| k3,n42:	1	| k3,n43:	1	| k3,n44:	1	| k3,n45:	1	| 

k4,n1:	1	| k4,n2:	1	| k4,n3:	1	| k4,n4:	1	| k4,n5:	1	| 
k4,n6:	1	| k4,n7:	1	| k4,n8:	1	| k4,n9:	1	| k4,n10:	49	| 
k4,n11:	49	| k4,n12:	49	| k4,n13:	61	| k4,n14:	87	| k4,n15:	87	| 
k4,n16:	97	| k4,n17:	107	| k4,n18:	129	| k4,n19:	137	| k4,n20:	145	| 
k4,n21:	139	| k4,n22:	151	| k4,n23:	135	| k4,n24:	123	| k4,n25:	109	| 
k4,n26:	93	| k4,n27:	65	| k4,n28:	47	| k4,n29:	31	| k4,n30:	29	| 
k4,n31:	1	| k4,n32:	1	| k4,n33:	1	| k4,n34:	1	| k4,n35:	1	| 
k4,n36:	1	| k4,n37:	1	| k4,n38:	1	| k4,n39:	1	| k4,n40:	1	| 
k4,n41:	1	| k4,n42:	1	| k4,n43:	1	| k4,n44:	1	| k4,n45:	1	| 

k5,n1:	1	| k5,n2:	1	| k5,n3:	1	| k5,n4:	1	| k5,n5:	1	| 
k5,n6:	1	| k5,n7:	1	| k5,n8:	1	| k5,n9:	1	| k5,n10:	1	| 
k5,n11:	1	| k5,n12:	1	| k5,n13:	1	| k5,n14:	1	| k5,n15:	61	| 
k5,n16:	61	| k5,n17:	61	| k5,n18:	71	| k5,n19:	93	| k5,n20:	129	| 
k5,n21:	137	| k5,n22:	145	| k5,n23:	171	| k5,n24:	183	| k5,n25:	209	| 
k5,n26:	203	| k5,n27:	203	| k5,n28:	187	| k5,n29:	173	| k5,n30:	155	| 
k5,n31:	135	| k5,n32:	91	| k5,n33:	63	| k5,n34:	39	| k5,n35:	37	| 
k5,n36:	1	| k5,n37:	1	| k5,n38:	1	| k5,n39:	1	| k5,n40:	1	| 
k5,n41:	1	| k5,n42:	1	| k5,n43:	1	| k5,n44:	1	| k5,n45:	1	| 

k6,n1:	1	| k6,n2:	1	| k6,n3:	1	| k6,n4:	1	| k6,n5:	1	| 
k6,n6:	1	| k6,n7:	1	| k6,n8:	1	| k6,n9:	1	| k6,n10:	1	| 
k6,n11:	1	| k6,n12:	1	| k6,n13:	1	| k6,n14:	1	| k6,n15:	1	| 
k6,n16:	1	| k6,n17:	1	| k6,n18:	1	| k6,n19:	1	| k6,n20:	1	| 
k6,n21:	71	| k6,n22:	71	| k6,n23:	71	| k6,n24:	79	| k6,n25:	97	| 
k6,n26:	127	| k6,n27:	177	| k6,n28:	173	| k6,n29:	185	| k6,n30:	195	| 
k6,n31:	207	| k6,n32:	205	| k6,n33:	221	| k6,n34:	177	| k6,n35:	149	| 
k6,n36:	121	| k6,n37:	83	| k6,n38:	49	| k6,n39:	47	| k6,n40:	1	| 
k6,n41:	1	| k6,n42:	1	| k6,n43:	1	| k6,n44:	1	| k6,n45:	1	| 

k7,n1:	1	| k7,n2:	1	| k7,n3:	1	| k7,n4:	1	| k7,n5:	1	| 
k7,n6:	1	| k7,n7:	1	| k7,n8:	1	| k7,n9:	1	| k7,n10:	1	| 
k7,n11:	1	| k7,n12:	1	| k7,n13:	1	| k7,n14:	1	| k7,n15:	1	| 
k7,n16:	1	| k7,n17:	1	| k7,n18:	1	| k7,n19:	1	| k7,n20:	1	| 
k7,n21:	1	| k7,n22:	1	| k7,n23:	1	| k7,n24:	1	| k7,n25:	1	| 
k7,n26:	1	| k7,n27:	1	| k7,n28:	79	| k7,n29:	79	| k7,n30:	79	| 
k7,n31:	85	| k7,n32:	99	| k7,n33:	115	| k7,n34:	149	| k7,n35:	183	| 
k7,n36:	179	| k7,n37:	153	| k7,n38:	147	| k7,n39:	111	| k7,n40:	107	| 
k7,n41:	61	| k7,n42:	59	| k7,n43:	1	| k7,n44:	1	| k7,n45:	1	| 

k8,n1:	1	| k8,n2:	1	| k8,n3:	1	| k8,n4:	1	| k8,n5:	1	| 
k8,n6:	1	| k8,n7:	1	| k8,n8:	1	| k8,n9:	1	| k8,n10:	1	| 
k8,n11:	1	| k8,n12:	1	| k8,n13:	1	| k8,n14:	1	| k8,n15:	1	| 
k8,n16:	1	| k8,n17:	1	| k8,n18:	1	| k8,n19:	1	| k8,n20:	1	| 
k8,n21:	1	| k8,n22:	1	| k8,n23:	1	| k8,n24:	1	| k8,n25:	1	| 
k8,n26:	1	| k8,n27:	1	| k8,n28:	1	| k8,n29:	1	| k8,n30:	1	| 
k8,n31:	1	| k8,n32:	1	| k8,n33:	1	| k8,n34:	1	| k8,n35:	1	| 
k8,n36:	85	| k8,n37:	85	| k8,n38:	85	| k8,n39:	83	| k8,n40:	81	| 
k8,n41:	79	| k8,n42:	77	| k8,n43:	75	| k8,n44:	73	| k8,n45:	1	| 

k9,n1:	1	| k9,n2:	1	| k9,n3:	1	| k9,n4:	1	| k9,n5:	1	| 
k9,n6:	1	| k9,n7:	1	| k9,n8:	1	| k9,n9:	1	| k9,n10:	1	| 
k9,n11:	1	| k9,n12:	1	| k9,n13:	1	| k9,n14:	1	| k9,n15:	1	| 
k9,n16:	1	| k9,n17:	1	| k9,n18:	1	| k9,n19:	1	| k9,n20:	1	| 
k9,n21:	1	| k9,n22:	1	| k9,n23:	1	| k9,n24:	1	| k9,n25:	1	| 
k9,n26:	1	| k9,n27:	1	| k9,n28:	1	| k9,n29:	1	| k9,n30:	1	| 
k9,n31:	1	| k9,n32:	1	| k9,n33:	1	| k9,n34:	1	| k9,n35:	1	| 
k9,n36:	1	| k9,n37:	1	| k9,n38:	1	| k9,n39:	1	| k9,n40:	1	| 
k9,n41:	1	| k9,n42:	1	| k9,n43:	1	| k9,n44:	1	| k9,n45:	89	| 

The worst case is 209 for k5/n25 (12 combinations). This is way less than the analysis given by the solution (9!*5/(9-5)! = 75600). And for more than half of the cases it simply returns.

I would say, maybe some times the complexity is just "not esitmatable".

1
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
09/12/2020 20:02Accepted4 ms6.8 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.